InforLorV4, Main, Exploration, bibRecord, 002797

Espace intrinsèque d'un graphe et recherche de communautés

Identifieur interne : 002797 ( Main/Exploration ); précédent : 002796; suivant : 002798

Espace intrinsèque d'un graphe et recherche de communautés

Auteurs : Alain Lelu [France] ; Martine Cadot [France]

Source :

Information interaction intelligence [ 1630-649X ] ; 2011.

RBID : Pascal:12-0146979

Descripteurs français

Pascal (Inist)
- Randomisation, Football, Forme convexe, Réseau social, Méthode spectrale, Laplacien, Graphe non orienté, Loi puissance, Loi probabilité, Réduction dimension.
mix :
- clustering de graphe, dimension intrinsèque, extraction de communautés, graphe, graphe sans échelle, laplacien d'un graphe, méthode densitaire de clustering, réduction de dimensions, test de randomisation, éboulis de Cattell..

English descriptors

KwdEn :
- Convex shape, Dimension reduction, Laplacian, Non directed graph, Power law, Probability distribution, Randomization, Soccer, Social network, Spectral method.
mix :
- Cattell's scree., density clustering method, dimensionality reduction, dominant eigen-subspace, graph, graph Laplacian, graph clustering, intrinsic dimension, randomization test, scale-free graph.

Abstract

La recherche de communautés dans un graphe se heurte à des problèmes épineux de représentation (formes convexes, recouvrantes, individus isolés...) dont l'abord optimal est réalisé par les méthodes spectrales, basées sur les dimensions propres du Laplacien de ce graphe. Déterminer le nombre de dimensions à prendre en considération est essentiel pour beaucoup d'applications. On s'attaque ici à ce problème dans le cadre de graphes non-orientés et non pondérés, qui inclut un type de graphe courant dans les applications de réseaux biologiques et sociaux, ceux munis d'une distribution des degrés de leurs nœuds en loi de puissance. Nous proposons à cet effet un test de randomisation, indépendant des lois de distribution. Après un petit exemple introductif, nous validons d'abord notre approche sur un graphe artificiel de ce type comportant deux communautés, puis sur deux graphes de test « Football League » et « Mexican Politician Network », où nous montrons à partir des résultats d'une méthode densitaire de clustering le caractère optimal du nombre de dimensions extraites.

Url:

https://hal.archives-ouvertes.fr/hal-00641128

Affiliations:

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr" level="a">Espace intrinsèque d'un graphe et recherche de communautés</title>
<author><name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">12-0146979</idno>
<date when="2011">2011</date>
<idno type="stanalyst">PASCAL 12-0146979 INIST</idno>
<idno type="RBID">Pascal:12-0146979</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000120</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000891</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000117</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000117</idno>
<idno type="wicri:doubleKey">1630-649X:2011:Lelu A:espace:intrinseque:d</idno>
<idno type="wicri:Area/Main/Merge">002841</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00641128</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00641128</idno>
<idno type="wicri:Area/Hal/Corpus">005B39</idno>
<idno type="wicri:Area/Hal/Curation">005B39</idno>
<idno type="wicri:Area/Hal/Checkpoint">001B29</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001B29</idno>
<idno type="wicri:doubleKey">1630-649X:2011:Lelu A:espace:intrinseque:d</idno>
<idno type="wicri:Area/Main/Merge">002119</idno>
<idno type="wicri:Area/Main/Curation">002797</idno>
<idno type="wicri:Area/Main/Exploration">002797</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr" level="a">Espace intrinsèque d'un graphe et recherche de communautés</title>
<author><name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="02"><s1>Université de Franche-Comté/LASELDI</s1>
<s2>Besançon</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Bourgogne-Franche-Comté</region>
<region type="old region">Franche-Comté</region>
<settlement type="city">Besançon</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="03"><s1>Université de Nancy/Département Informatique</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Grand Est</region>
<region type="old region">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><inist:fA14 i1="04"><s1>Institut des Sciences de la Communication du CNRS</s1>
<s2>Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region">Île-de-France</region>
<region type="old region">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Information interaction intelligence</title>
<title level="j" type="abbreviated">Inf. interact. intell.</title>
<idno type="ISSN">1630-649X</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Information interaction intelligence</title>
<title level="j" type="abbreviated">Inf. interact. intell.</title>
<idno type="ISSN">1630-649X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Convex shape</term>
<term>Dimension reduction</term>
<term>Laplacian</term>
<term>Non directed graph</term>
<term>Power law</term>
<term>Probability distribution</term>
<term>Randomization</term>
<term>Soccer</term>
<term>Social network</term>
<term>Spectral method</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Randomisation</term>
<term>Football</term>
<term>Forme convexe</term>
<term>Réseau social</term>
<term>Méthode spectrale</term>
<term>Laplacien</term>
<term>Graphe non orienté</term>
<term>Loi puissance</term>
<term>Loi probabilité</term>
<term>Réduction dimension</term>
</keywords>
<keywords scheme="mix" xml:lang="en"><term>Cattell's scree.</term>
<term>density clustering method</term>
<term>dimensionality reduction</term>
<term>dominant eigen-subspace</term>
<term>graph</term>
<term>graph Laplacian</term>
<term>graph clustering</term>
<term>intrinsic dimension</term>
<term>randomization test</term>
<term>scale-free graph</term>
</keywords>
<keywords scheme="mix" xml:lang="fr"><term>clustering de graphe</term>
<term>dimension intrinsèque</term>
<term>extraction de communautés</term>
<term>graphe</term>
<term>graphe sans échelle</term>
<term>laplacien d'un graphe</term>
<term>méthode densitaire de clustering</term>
<term>réduction de dimensions</term>
<term>test de randomisation</term>
<term>éboulis de Cattell.</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr">La recherche de communautés dans un graphe se heurte à des problèmes épineux de représentation (formes convexes, recouvrantes, individus isolés...) dont l'abord optimal est réalisé par les méthodes spectrales, basées sur les dimensions propres du Laplacien de ce graphe. Déterminer le nombre de dimensions à prendre en considération est essentiel pour beaucoup d'applications. On s'attaque ici à ce problème dans le cadre de graphes non-orientés et non pondérés, qui inclut un type de graphe courant dans les applications de réseaux biologiques et sociaux, ceux munis d'une distribution des degrés de leurs nœuds en loi de puissance. Nous proposons à cet effet un test de randomisation, indépendant des lois de distribution. Après un petit exemple introductif, nous validons d'abord notre approche sur un graphe artificiel de ce type comportant deux communautés, puis sur deux graphes de test « Football League » et « Mexican Politician Network », où nous montrons à partir des résultats d'une méthode densitaire de clustering le caractère optimal du nombre de dimensions extraites.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Bourgogne-Franche-Comté</li>
<li>Franche-Comté</li>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Île-de-France</li>
</region>
<settlement><li>Besançon</li>
<li>Nancy</li>
<li>Paris</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
</region>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Cadot, Martine" sort="Cadot, Martine" uniqKey="Cadot M" first="Martine" last="Cadot">Martine Cadot</name>
<name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
<name sortKey="Lelu, Alain" sort="Lelu, Alain" uniqKey="Lelu A" first="Alain" last="Lelu">Alain Lelu</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002797 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002797 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:12-0146979
   |texte=   Espace intrinsèque d'un graphe et recherche de communautés
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Espace intrinsèque d'un graphe et recherche de communautés

Espace intrinsèque d'un graphe et recherche de communautés

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.